import java.util.*;


/**
 * @program: leetcode128
 * @author: JCM
 * @create: 2023-02-22 19:38
 * @description:
 **/
public class Main {

    //  排序法，先使用  sort 将数组排序，然后直接遍历数组
    public int longestConsecutive(int[] nums) {
        if(nums.length == 0 || nums.length == 1) return nums.length;
        Arrays.sort(nums);
        int ret = 1;
        int max = ret;
        for(int i = 0; i < nums.length-1; i++) {
            if(nums[i] == nums[i+1]-1) {
                ret++;
            }else if(nums[i] == nums[i+1]) {
                continue;
            }else {
                ret = 1;
            }
            if(max < ret) {
                max = ret;
            }
        }
        return max;
    }

    //
    public int longestConsecutive2(int[] nums) {
        //建立一个存储所有数据的哈希表，同时起到去重的作用
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }
        int ans = 0;
        // 遍历去重后的所有数字
        for (int num : set) {
            int cur = num;
            //  当  num-1 不存在时，开始寻找 num+1，num+2，num+3...
            if (!set.contains(cur-1)) {
                while(set.contains(cur+1)) {
                    cur++;
                }
            }
            ans = Math.max(ans,cur - num + 1);
        }
        return ans;
    }

}
